package srcInterviewPrep;

import java.util.ArrayList;
import java.util.List;

public final class FloodFill
{
    public static void StartFloodFill(boolean[][] m, int i, int j, int numRows, int numCols)
    {
        boolean expectedColor = !m[i][j];

        FloodFillRecursive(m, i, j, expectedColor, numRows, numCols);
    }

    private static void FloodFillRecursive(boolean[][]m, int i, int j, boolean expectedColor, int numRows, int numCols)
    {
        if (m[i][j] == expectedColor)
        {
            return;
        }

        m[i][j] = expectedColor;

        for (Neighbor nbor : GetNeighbors(i,j, numRows, numCols))
        {
            FloodFillRecursive(m, nbor.i, nbor.j, expectedColor, numRows, numCols);
        }
    }

    private static List<Neighbor> GetNeighbors(int i, int j, int numRows, int numCols)
    {
        Neighbor left = new Neighbor(i, j-1);
        Neighbor right = new Neighbor(i, j+1);
        Neighbor top = new Neighbor(i+1, j);
        Neighbor bottom = new Neighbor(i-1, j);

        List<Neighbor> validNeighbors = new ArrayList<Neighbor>(4);

        if (IsValidNeighbor(left, numRows, numCols))
        {
            validNeighbors.add(left);
        }

        if (IsValidNeighbor(right, numRows, numCols))
        {
            validNeighbors.add(right);
        }

        if (IsValidNeighbor(top, numRows, numCols))
        {
            validNeighbors.add(top);
        }

        if (IsValidNeighbor(bottom, numRows, numCols))
        {
            validNeighbors.add(bottom);
        }

        return validNeighbors;
    }

    private static boolean IsValidNeighbor(Neighbor n, int numRows, int numCols)
    {
        if (n.i >= 0
            && n.i < numRows
            && n.j >= 0
            && n.j < numCols)
        {
            return true;
        }

        return false;
    }

    private static final class Neighbor
    {
        private int i;
        private int j;

        private Neighbor(int x, int y)
        {
            i = x;
            j = y;
        }
    }
}
